Many large scale data processing systems now employ a multiplicity of independent computer/disk systems, all of which operate in parallel on discrete portions of a problem. An independent computer/disk is called a node of the multi-processing system. In such systems, it can be the case that data files are distributed across the system so as to balance nodal work loads and to protect against significant losses of data should one or more nodes malfunction.
A variety of techniques have been proposed to enable data reconstruction in the event of failure of one or more nodes. For instance, in U.S. Pat. No. 4,722,085 to Flora, a relatively large number of independently operating disk subsystems are coupled to a read/write interface containing error circuitry and organization circuitry. Each data word read into the system has its bits spread across the disk files so that only one bit of each word is written to a particular physical disk file. This assures that a single bit error will not cause a fault since it is automatically corrected by parity correction in the error circuitry. U.S. Pat. No. 4,817,035 to Timsit also describes a similar, bit-oriented, distributed storage across a plurality of disk units.
In U.S. Pat. No. 4,761,785 to Clark et al., assigned to the same assignee as this application, another version of distributed storage is described to enable data 1 in the event of a malfunction. The Clark et al. system employs the concept of the spreading of data blocks across a plurality of disk drives and exclusive-Or'ing a series of blocks to derive a parity check block. Each disk drive contains the same number of block physical address areas. Disk physical address areas with the same unit address ranges are referred to as "stripes". Each stripe has n-1 blocks of data written across n-1 disk drives and a parity block on another disk drive, which parity block contains parity for the n-1 blocks of the stripe. Since a stripe of blocks is written across a plurality of disk drives, the failure of any one disk drive can be accommodated by employing the parity block and exclusive-Or'ing it with all remaining blocks, to derive the lost data block.
While the system described by Clark et al. does effectively protect data blocks from single disk failures, it exhibits drawbacks First, and most importantly, it is dependent for its structure upon physical block positions in individual disk drives. In other words, the parity for the n-1 blocks is derived based upon each block's physical location on a disk. Thus, if any movement of data blocks is contemplated within a disk drive, the parity must be rewritten each time a block is moved. Furthermore, when a complete file is removed from a disk drive, the parity constructed by Clark et al. may or may not be relevant, depending upon where the file blocks were located in the disk structure. (The parity is only applicable to physical disk addresses and not to the file blocks per se, so if the file blocks are not exclusively coincident with the stripes, the parity structure must be maintained even after the file has been deleted.) Finally, employing a parity structure such as described by Clark et al. requires substantial constraints be placed upon the system programmer in terms of where data blocks are to be allocated on the disk drive surface.
Accordingly, it is an object of this invention to provide for a parallel computing system, a file-based, parity protection structure which is integral to the file structure rather than the physical disk structure.
It is another object of this invention to provide a block-parity protection method which enables data blocks to be placed anywhere on an array of disk files, while still retaining file parity protection.
It is still another object of this invention to provide a redundant parity protection system for distributed computing, file-based data that enables generated parity blocks to move with a data file and to still be relevant to and only to the data file, upon removal of the file from disks.